#include<iostream>
#include<queue>
using namespace std;

template < typename Comparable >
class BinarySearchTree
{
public:
    BinarySearchTree()
    {}

    ~BinarySearchTree()
    {};

    void insert(const Comparable& x)
    {
        insert(x, root);
    }

    void inorder() { inorder(root); }
    //成员参数队列s用于按序储存中序遍历后遍历到的BinaryNode，便于后续对容器进行覆盖操作
    queue<Comparable> s;

    int count_settree = 0;

private:
    struct BinaryNode
    {
        Comparable element;
        BinaryNode* left;
        BinaryNode* right;

        BinaryNode(const Comparable& theElement, BinaryNode* lt, BinaryNode* rt)
            : element(theElement), left{ lt }, right{ rt } {}

        BinaryNode(Comparable&& theElement, BinaryNode* lt, BinaryNode* rt)
            : element{ std::move(theElement) }, left{ lt }, right{ rt } { }

    };

    BinaryNode* root=nullptr;
 

    void insert(const Comparable& x, BinaryNode*& t)
    {
        if (t == nullptr)
        {
            t = new BinaryNode(x, nullptr, nullptr);
            count_settree++;
        }
        else if (x < t->element)
        {
            insert(x, t->left);
            count_settree++;
        }
        else if (x > t->element)
        {
            insert(x, t->right);
            count_settree++;
        }
        else;
    }
    //通过递归实现中序遍历，按序讲解点放入队列s
    void inorder(const BinaryNode* t)
    {
        if (t == nullptr) return;
        inorder(t->left);
        s.push(t->element);
        inorder(t->right);

    }
}; 
